package com.cat.chapter037;

import java.util.ArrayList;
import java.util.List;

/**
 * @author cat
 * @description https://leetcode.cn/problems/path-sum-ii/
 * @create 2025/6/18 19:30
 * @since JDK17
 */

public class Solution03 {
    List<List<Integer>> ans = new ArrayList<>();
    List<Integer> list = new ArrayList<>();
    public List<List<Integer>> pathSum(TreeNode root, int targetSum) {
        if (root != null) {
            list.add(root.val);
            f(root, root.val, targetSum);
        }
        return ans;
    }

    public void f(TreeNode root, int cur, int targetSum) {
        if (root.left == null && root.right == null) {
            if (cur == targetSum) {
                ans.add(new ArrayList(list));
            }
            return;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        if (left != null) {
            list.add(left.val);
            f(left, cur + left.val, targetSum);
            list.remove(list.size() - 1);
        }
        if (right != null) {
            list.add(right.val);
            f(right, cur + right.val, targetSum);
            list.remove(list.size() - 1);
        }
    }
}
